<?php
/*
 * 二叉树的序列化和反序列化
 * 【题目】二叉树被记录成文件的过程叫作二叉树的序列化，通过文件内容重建原来二叉树的过程叫作二叉树的反序列化。
 * 给定一棵二叉树的头节点head，并已知二叉树节点值的类型为32位整型。
 * 请设计一种二叉树序列化和反序列化的方案，并用代码实现。
 * 【要求】
 * 1，实现先序遍历序列化与反序列化
 * 2，实现按层遍历序列化与反序列化
 *
 *                  1
 *                /   \
 *               2     3
 *             /  \   / \
 *            4   5  6   7
 * 序列化结果可写为: 1_2_4_#_#_5_#_#_3_6_#_#_7_#_#_
 */

require_once '../../../class/TreeNode.class.php';
$arr = [1,2,3,4,5,6,7];
$head = generateTreeByArray($arr);
$obj = new Code_01_SerializeTree();

$res1 = $obj->serialByPre($head);
echo $res1 . PHP_EOL;
$node1 = $obj->unserialByPre($res1);
//var_dump($node1);

$res2 = $obj->serialByLevel($head);
echo $res2 . PHP_EOL;
$node2 = $obj->unserialByLevel($res2);
//var_dump($node2);


class Code_01_SerializeTree
{
    // 先序的序列化
    public function serialByPre($head)
    {
        if ($head == null) {
            return '#_';
        }
        $res = $head->val . '_';
        $res .= $this->serialByPre($head->left);
        $res .= $this->serialByPre($head->right);
        return $res;
    }

    // 先序的反序列化
    public function unserialByPre($str)
    {
        $arr = explode('_', $str);
        $queue = new SplQueue();
        for ($i = 0, $len = count($arr); $i < $len; $i++) {
            $queue->enqueue($arr[$i]);
        }
        return $this->_unserialByPre($queue);
    }

    protected function _unserialByPre($queue)
    {
        $val = $queue->dequeue();
        if ($val == '#') {
            return null;
        }
        $head = new TreeNode(intval($val));
        $head->left = $this->_unserialByPre($queue);
        $head->right = $this->_unserialByPre($queue);
        return $head;
    }

    // 按层的序列化
    public function serialByLevel($head)
    {
        if ($head == null) {
            return '#_';
        }
        $res = $head->val . '_';
        $queue = new SplQueue();
        $queue->enqueue($head);
        while (!$queue->isEmpty()) {
            $head = $queue->dequeue();
            if ($head->left != null) {
                $res .= $head->left->val . '_';
                $queue->enqueue($head->left);
            } else {
                $res .= '#_';
            }
            if ($head->right != null) {
                $res .= $head->right->val . '_';
                $queue->enqueue($head->right);
            } else {
                $res .= '#_';
            }
        }
        return $res;
    }

    public function unserialByLevel($str)
    {
        $arr = explode('_', $str);
        $index = 0;
        $head = $this->_generateNodeByString($arr[$index++]);
		$queue = new SplQueue();
		if ($head != null) {
            $queue->enqueue($head);
        }
		while (!$queue->isEmpty()) {
            $node = $queue->dequeue();
            $node->left = $this->_generateNodeByString($arr[$index++]);
            $node->right = $this->_generateNodeByString($arr[$index++]);
            if ($node->left != null) {
                $queue->enqueue($node->left);
            }
            if ($node->right != null) {
                $queue->enqueue($node->right);
            }
        }
		return $head;
    }

    protected function _generateNodeByString($str)
    {
        if ($str == '#') {
            return null;
        }
        return new TreeNode(intval($str));
    }
}
